package com.algorithm.note01Sort.entity;

/**
 * 排序类
 */
public class SortEntity {
    /**
     * 选择排序:循环数组，以当前值逐个比较其后所有的值，遇到比它小的交换，两个值得位置进行交换
     * @param arr
     * @return
     */
    public int[] selectSort(int[] arr){
        //排除无效数组
        if(arr == null || arr.length == 1){
            return arr;
        }

        //循环整个数组
        for (int i = 0; i < arr.length - 1; i++){
            //循环当前值之后的所有值
            for (int j = i + 1; j < arr.length; j ++){
                //发现对比小的值，交换位置
                if(arr[i] > arr[j]){
                    swap(arr, i, j);
                }
            }
        }
        return arr;
    }

    /**
     * 冒泡排序:循环数组，逐个比较相邻的两个值，当前一个值大于后一个值，交换两者位置
     * 优化：某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。
     * @param arr
     * @return
     */
    public int[] bubbleSort(int[] arr){
        //排除无效数组
        if(arr == null || arr.length == 1){
            return arr;
        }

        //逐个比较相邻的两个值，当前一个值大于后一个值，交换两者位置。
        //比较一轮下来，最后一个值一定是最大值，因此在外包一层循环，从最后一个值往前遍历整个数组，内部按照冒泡的方式进行比较。
        for (int n = arr.length - 1; n > 0; n--) {
            //某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。
            boolean flag = false;

            for (int i = 0; i < n; i++) {
                //获取其后一个位置的值
                int j = i + 1;
                //当前值大于其后一个值
                if (arr[i] > arr[j]){
                    swap(arr, i, j);
                }

                flag = true;
            }

            // 内循环未交换任何元素，则跳出
            if (!flag){
                break;
            }
        }
        return arr;
    }

    /**
     * 交换数组中两个下标的值
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
